2681. 英雄的力量

Similar Question

Solution Tips

方案一: 回溯 - 组合 + 数学

空间复杂度超了

即使去掉 chosen 也会超时, 回溯算法的时间复杂度是指数级的.

var sumOfPower = function(nums) {
    // 首先这里有一个组合, 要先选取不同的组合
    // 回溯选取, 每次 push 的时候只需要比较最大和最小有没有变化就行了
    let res = 0;
    // const map = new Map();
    backtracking([], 0, Number.MAX_SAFE_INTEGER, 0);

    function backtracking(chosen, max, min, curIndex) {
        if (curIndex >= nums.length) {
            const key = `${max}&${min}`;
            // if (map.has(`${max}&${min}`)) return res += map.get(key);
            // 根据 max 和 min 计算
            if (chosen.length > 0) {
                // 得用大数乘法, 但是很多 max 和 min 其实是一样的, 没必要重复算
                // res += (max * max * min) % (Math.pow(10, 9) + 7)
                // 等于分别取模然后相乘
                sum = (((max * max) % (Math.pow(10, 9) + 7)) * min) % (Math.pow(10, 9) + 7);
                // map.set(key, sum);
                res += sum;
            }
            return;
        }

        // 不选择当前 nums 的 case
        backtracking(chosen, max, min, curIndex + 1);
        // 选择当前 nums 的 case
        chosen.push(nums[curIndex]);
        max = Math.max(max, nums[curIndex]);
        min = Math.min(min, nums[curIndex]);
        backtracking(chosen, max, min, curIndex + 1);
    }

    // function bigMultiple(a, b) {

    // }

    return res;
};

// console.log(sumOfPower([2, 1, 4]))
console.log(sumOfPower([2, 1, 4]))

两个 for 循环并不能找到所有的组合, [1, 4] 就漏掉了

var sumOfPower = function(nums) {
    // 排序之后选
    nums = nums.sort((a, b) => a - b);
    let res = 0;

    for (let i = 0; i < nums.length; i++) {
        for (let j = i; j < nums.length; j++) {
            // 选择 [i, j] 的区间, min 为 i, max 为 j
            const max = nums[j];
            const min = nums[i];
            const sum = (((max * max) % (Math.pow(10, 9) + 7)) * min) % (Math.pow(10, 9) + 7);
            console.log('sum', sum);
            res += sum
        }
    }

    return res;
};

console.log(sumOfPower([1, 2, 4]))